#define MAX_ARR 1000

typedef bool(*Compare)(int a, int b);

typedef struct{
    int count;
    int arr[MAX_ARR];       // 保存完全二叉树
    Compare cmp;

private:
    void swap(int *a, int *b){
        int tmp = *a;
        *a = *b;
        *b = tmp;
    }

    /**
     * @brief Heap Adjust Up
     * 
     * @param C child index
     */
    void bub_up(int C){
        int child=C;
        while(child>0){
            int dad = (child - 1) / 2;          // 公式， parent=(child-1)/2
            if(!cmp(arr[dad], arr[child])){
                swap(&arr[dad], &arr[child]);
                child = dad;
            }else break;
        }
    }

    /**
     * @brief Heap Adjust Down
     * 
     * @param D dad or parent index
     */
    void bub_down(int D){
        int dad = D;
        while(dad < count/2){       // count/2
            int child = 2*dad+2;                // right child
            if(child>=count || cmp(arr[child-1], arr[child])) child--; 
            if(!cmp(arr[dad], arr[child])){
                swap(&arr[dad], &arr[child]);
                dad = child;
            }else break;
        }
    }
public:
    void push(int value){
        arr[count++] = value;
        bub_up(count-1);    // 最后一个元素的索引为count-1
    }

    int pop(){
        // assert(count>0)
        int ret = arr[0];       // 堆顶元素
        arr[0] = arr[--count];  // 将堆尾元素放入堆顶
        bub_down(0);
        return ret;
    }

    void modify(int idx){
        bub_down(idx);
        bub_up(idx);
    }

    void sort(int input_arr[], int len){
        // assert len < MAX_ARR
        // create Heap
        for(int i=0;i<len;i++){
            push(input_arr[i]);
        }
        // pop
        int cnt=0;
        while(count>0){
            input_arr[cnt++] = pop();
        }
    }

}Heap;

#include<stdio.h>

bool bigger_than(int a, int b){
    return a > b;
}

bool less_than(int a, int b){
    return a < b;
}

void print_arr(int arr[], int len, const char* name){
    printf("%s@%d:", name, len);
    for(int i=0;i<len;i++) printf("%d ", arr[i]);
    printf("\n");
}

void test_heap_sort2(){
    int input_arr[10] = {3, 6, 1, 4, 12, 7, 8, 46, 31, 0};
    int len = 10;

    Heap heap;
    heap.count = 0;
    heap.cmp = less_than;

    print_arr(input_arr, len, "Before");
    heap.sort(input_arr, len);
    print_arr(input_arr, len, "After");
}

int main(){
    test_heap_sort2();
}
